ICPC Live Archive/4808 - Digits Count/4808.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 vector<int> num;
  28
  29
  30 void print(const vector<int> &v) {
  31     for (int i = 0; i < v.size(); ++i) {
  32         if (i > 0) printf(" ");
  33         printf("%d", v[i]);
  34     }
  35     printf("\n");
  36 }
  37
  38 int ten(int e) {
  39     assert(e >= 0);
  40     int ans = 1;
  41     while (e--) ans *= 10;
  42     return ans;
  43 }
  44
  45 int assemble(int i) {
  46     assert(i >= -1);
  47     int ans = 0;
  48     for (int k = i; k >= 0; --k) {
  49         ans = 10 * ans + num[k];
  50     }
  51     return ans;
  52 }
  53
  54 vector<int> memo[10][2];
  55
  56 vector<int> f(int i, bool m) {
  57     if (i < 0) {
  58         return vector<int>(10, 0);
  59     }
  60
  61     if (memo[i][m].size() > 0) return memo[i][m];
  62
  63     vector<int> ans(10, 0);
  64
  65     int limit = (m ? 9 : num[i] - 1);
  66     for (int k = 0; k <= limit; ++k) {
  67         vector<int> s = f(i - 1, true);
  68         s[k] += ten(i);
  69         for (int j = 0; j < 10; ++j) ans[j] += s[j];
  70     }
  71
  72     if (!m) {
  73         vector<int> s = f(i - 1, false);
  74         s[num[i]] += assemble(i - 1) + 1;
  75         for (int j = 0; j < 10; ++j) ans[j] += s[j];
  76     }
  77     memo[i][m] = ans;
  78     return ans;
  79 }
  80
  81 vector<int> f(int x) {
  82     num.clear();
  83     while (x > 0) num.push_back(x % 10), x /= 10;
  84     for (int i = 0; i <= 10; ++i) {
  85         memo[i][0].clear(), memo[i][1].clear();
  86     }
  87     vector<int> ans = f(num.size() - 1, false);
  88     ans[0] -= (ten(num.size()) - 1) / 9;
  89     // for (int i = num.size() - 1; i >= 0; --i) {
  90     //     assert(ans[0] >= ten(i));
  91     //     ans[0] -= ten(i);
  92     // }
  93     return ans;
  94 }
  95
  96 void bruteforce(int a) {
  97     vector<int> ans(10, 0);
  98     for (int i = 1; i <= a; ++i){
  99         int x = i;
 100         while (x > 0) ans[x % 10]++, x /= 10;
 101     }
 102     printf("Bruteforced answer for i=%d: ", a);
 103     print(ans);
 104 }
 105
 106 int main(){
 107     // vector<int> a = f(1);
 108     // print(a);
 109     // for (int i = 1; i <= 100; ++i) {
 110     //     printf("i = %d: ", i);
 111     //     print(f(i));
 112     // }
 113     int a, b;
 114     while (cin >> a >> b) {
 115         if (a == 0 and b == 0) break;
 116         vector<int> ans = f(b);
 117         if (a - 1 > 0) {
 118             vector<int> remove = f(a - 1);
 119             for (int i = 0; i < 10; ++i) ans[i] -= remove[i];
 120         }
 121         //if (a - 1 > 0) { printf("f(%d) = ", a - 1); print(f(a - 1)); }
 122         //printf("f(%d) = ", b); print(f(b));
 123         //bruteforce(b);
 124         print(ans);
 125     }
 126     return 0;
 127 }